# 二叉树的最近公共祖先： https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
            这道题我想到的是后序遍历， 左，右， 根
            当一颗子树的左右子树或者本身包含了 这两个节点时，就返回该节点
        """
        def dfs(node):
            if not node: return None
            a = dfs(node.left)
            b = dfs(node.right)

            # 1. 如果当前节点 等于 p 或 q，返回当前节点，别管是否 当前树的 子树是否有另一个都返回当前节点
            if node == p or node == q:
                return node
            # 2. 如果都找到了，直接返回 node
            if a and b:
                return node
            # 3. 只有一个，就返回有的， 代表当前树有一个（当前树也是其父节点的子树）
            elif a is not None:
                return a
            elif b is not None:
                return b
            # 4. 一个都没有，就返回None， 当前树，没有找到匹配节点
            else:
                return None
            
        return dfs(root)




